package main

import (
	"fmt"
	"strconv"
	"strings"
)

func findNumbers(nums []int) int {
	result := 0
	for i := 0; i < len(nums); i++ {
		if len(strconv.Itoa(nums[i]))%2 == 0 {
			result++
		}
	}
	return result
}

func defangIPaddr(address string) string {
	return strings.ReplaceAll(address, ".", "[.]")
}

type ListNode struct {
	Val  int
	Next *ListNode
}

func mySqrtTool(x, y int) int {

	if y*y <= x && (y+1)*(y+1) > x {
		return y
	}
	//y = x/2
	if (y/2)*(y/2) < x {
		return mySqrtTool(x, y-1)
	}
	if y*y > x {
		return mySqrtTool(x, y/2)
	}
	return mySqrtTool(x, y*2)
}

func mySqrt(x int) int {
	return mySqrtTool(x, x)
}

//表面是删除当前节点，实际上需要删除下一个节点，并且把数据复制给当前节点即可
func deleteNode(node *ListNode) {
	if node == nil {
		return

	}
	if node.Next == nil {
		return
	}
	p := node.Next
	n := node

	n.Val = p.Val
	n.Next = p.Next
	//
	// n.Next = nil
	// n = nil

}

func decompressRLElist(nums []int) []int {
	result := []int{}
	for i := 0; i < len(nums); i += 2 {
		for j := 0; j < nums[i]; j++ {
			result = append(result, nums[i+1])
		}
	}
	return result
}

/*
nums = [0,1,2,3]
n[i] 存放数组nums中数据=i 的个数
d[i] = d[i-1]+n[i-1]
*/

func MaxMin(nums []int) (big, small int) {
	l := len(nums)
	if l == 0 {
		return 0, 0
	}
	var i int
	if l%2 == 0 {
		i = 2
		if nums[0] > nums[1] {
			big = nums[0]
			small = nums[1]
		} else {
			big = nums[1]
			small = nums[0]
		}
	} else {
		big = nums[0]
		small = nums[0]
		i = 1
	}
	for ; i < l; i += 2 {
		if nums[i] > nums[i+1] {
			if big < nums[i] {
				big = nums[i]
			}
			if small > nums[i+1] {
				small = nums[i+1]
			}
		} else {
			if big < nums[i+1] {
				big = nums[i+1]
			}
			if small > nums[i] {
				small = nums[i]
			}
		}
	}
	return
}

func smallerNumbersThanCurrent(nums []int) []int {
	l := len(nums)
	result := make([]int, l)
	big, small := MaxMin(nums)
	n := make([]int, big-small+1)
	//初始化n为0
	for i := 0; i < big-small+1; i++ {
		n[i] = 0
	}
	//计算n[i]的个数
	for i := 0; i < l; i++ {
		n[nums[i]-small] += 1
	}
	dp := make([]int, big-small+1)
	dp[0] = 0
	for i := small; i < big; i++ {
		dp[i-small+1] = dp[i-small] + n[i-small]
	}
	for i := 0; i < l; i++ {
		result[i] = dp[nums[i]-small]
	}
	fmt.Println(result)
	return result
}

func smallerNumbersThanCurrent2(nums []int) []int {
	l := len(nums)
	result := make([]int, l)
	for i := 0; i < l; i++ {
		result[i] = 0
	}
	for i := 0; i < l-1; i++ {
		for j := i + 1; j < l; j++ {
			if nums[i] > nums[j] {
				result[i] += 1

			}
			if nums[i] < nums[j] {
				result[j] += 1
			}
		}
	}
	return result
}

func main() {
	//a := findNumbers([]int{123,4343,43,1234})
	//fmt.Println(a)
	//b := smallerNumbersThanCurrent([]int{1, 2, 2, 3, 4})
	//fmt.Println(b)
	a := mySqrt(100, 100/2)
	fmt.Println(a)
}
